00001
00002
00003
00004 #include <stdio.h>
00005 #include <stdlib.h>
00006 #include <string.h>
00007 #include "graph.h"
00008 #include "instances.inc"
00009
00010
00011 template <typename captype, typename tcaptype, typename flowtype>
00012 Graph<captype, tcaptype, flowtype>::Graph(int node_num_max, int edge_num_max, void (*err_function)(char *))
00013 : node_num(0),
00014 nodeptr_block(NULL),
00015 error_function(err_function)
00016 {
00017 if (node_num_max < 16) node_num_max = 16;
00018 if (edge_num_max < 16) edge_num_max = 16;
00019
00020 nodes = (node*) malloc(node_num_max*sizeof(node));
00021 arcs = (arc*) malloc(2*edge_num_max*sizeof(arc));
00022 if (!nodes || !arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00023
00024 node_last = nodes;
00025 node_max = nodes + node_num_max;
00026 arc_last = arcs;
00027 arc_max = arcs + 2*edge_num_max;
00028
00029 maxflow_iteration = 0;
00030 flow = 0;
00031 }
00032
00033 template <typename captype, typename tcaptype, typename flowtype>
00034 Graph<captype,tcaptype,flowtype>::~Graph()
00035 {
00036 if (nodeptr_block)
00037 {
00038 delete nodeptr_block;
00039 nodeptr_block = NULL;
00040 }
00041 free(nodes);
00042 free(arcs);
00043 }
00044
00045 template <typename captype, typename tcaptype, typename flowtype>
00046 void Graph<captype,tcaptype,flowtype>::reset()
00047 {
00048 node_last = nodes;
00049 arc_last = arcs;
00050 node_num = 0;
00051
00052 if (nodeptr_block)
00053 {
00054 delete nodeptr_block;
00055 nodeptr_block = NULL;
00056 }
00057
00058 maxflow_iteration = 0;
00059 flow = 0;
00060 }
00061
00062 template <typename captype, typename tcaptype, typename flowtype>
00063 void Graph<captype,tcaptype,flowtype>::reallocate_nodes(int num)
00064 {
00065 int node_num_max = (int)(node_max - nodes);
00066 node* nodes_old = nodes;
00067
00068 node_num_max += node_num_max / 2;
00069 if (node_num_max < node_num + num) node_num_max = node_num + num;
00070 nodes = (node*) realloc(nodes_old, node_num_max*sizeof(node));
00071 if (!nodes) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00072
00073 node_last = nodes + node_num;
00074 node_max = nodes + node_num_max;
00075
00076 if (nodes != nodes_old)
00077 {
00078 arc* a;
00079 for (a=arcs; a<arc_last; a++)
00080 {
00081 a->head = (node*) ((char*)a->head + (((char*) nodes) - ((char*) nodes_old)));
00082 }
00083 }
00084 }
00085
00086 template <typename captype, typename tcaptype, typename flowtype>
00087 void Graph<captype,tcaptype,flowtype>::reallocate_arcs()
00088 {
00089 int arc_num_max = (int)(arc_max - arcs);
00090 int arc_num = (int)(arc_last - arcs);
00091 arc* arcs_old = arcs;
00092
00093 arc_num_max += arc_num_max / 2; if (arc_num_max & 1) arc_num_max ++;
00094 arcs = (arc*) realloc(arcs_old, arc_num_max*sizeof(arc));
00095 if (!arcs) { if (error_function) (*error_function)("Not enough memory!"); exit(1); }
00096
00097 arc_last = arcs + arc_num;
00098 arc_max = arcs + arc_num_max;
00099
00100 if (arcs != arcs_old)
00101 {
00102 node* i;
00103 arc* a;
00104 for (i=nodes; i<node_last; i++)
00105 {
00106 if (i->first) i->first = (arc*) ((char*)i->first + (((char*) arcs) - ((char*) arcs_old)));
00107 }
00108 for (a=arcs; a<arc_last; a++)
00109 {
00110 if (a->next) a->next = (arc*) ((char*)a->next + (((char*) arcs) - ((char*) arcs_old)));
00111 a->sister = (arc*) ((char*)a->sister + (((char*) arcs) - ((char*) arcs_old)));
00112 }
00113 }
00114 }